package cn.jietuo.first.class04;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2020/7/8
 * @description:
 */
public class Code04_Heap02 {

    public static class MyHeap<T> {
        private List<T> heap;
        private int heapSize;
        private HashMap<T, Integer> indexMap;
        private Comparator<? super T> comparator;

        public MyHeap(Comparator<? super T> comparator) {
            heapSize = 0;
            heap = new ArrayList<T>();
            indexMap = new HashMap<T, Integer>();
            this.comparator = comparator;
        }

        public boolean isEmpty() {
            return heapSize == 0;
        }

        public int size() {
            return heapSize;
        }

        public boolean contions(T k) {
            return indexMap.containsKey(k);
        }

        public void push(T value) {
            heap.add(value);
            indexMap.put(value, heapSize);
            heapInsert(heap, heapSize++);
        }

        public T pop() {
            T ans = heap.get(0);
            int end = heapSize - 1;
            swap(heap, 0, end);
            heap.remove(end);
            indexMap.remove(ans);
            heapify(heap, 0, --heapSize);
            return ans;
        }

        private void heapInsert(List<T> heap, int index) {
            while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
                swap(heap, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        public void regin(T value) {
            // 找到这个位置的值
            Integer index = indexMap.get(value);
            heapInsert(heap, index);
            heapify(heap, index, heapSize);
        }

        private void heapify(List<T> heap, Integer index, int heapSize) {
            int left = index * 2 + 1;
            while (left <= heapSize) {
                int largest = left + 1 <= heapSize && comparator.compare(heap.get(left + 1), heap.get(left)) < 0 ? left + 1 : left;
                largest = comparator.compare(heap.get(largest), heap.get(index)) < 0 ? largest : index;
                if (largest == index) {
                    return;
                }
                swap(heap, largest, index);
                index = largest;
                left = index * 2 + 1;
            }
        }

        private void swap(List<T> heap, int i, int j) {
            T o1 = heap.get(i);
            T o2 = heap.get(j);

            heap.set(j, o1);
            heap.set(i, o2);
            indexMap.put(o1, j);
            indexMap.put(o2, i);
        }
    }
}
